package com.lwt.codetop.queue;

// 239. 滑动窗口最大值

import sun.security.util.ArrayUtil;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 思路：滑动窗口 + 单调队列（维护窗口的一个单调序列，确保最大值位于队头）
 */
public class SlidingWindowMaximum {
    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        int[] res = maxSlidingWindow(nums, k);
        for (int re : res) {
            System.out.print(re + " ");
        }
    }

    private static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> q = new LinkedList<>();
        int[] res = new int[n - k + 1];
        int idx = 0;
        for (int i = 0; i < n; i++) {// i这里是窗口的右端点
            // 移除过期元素（说明队头元素已经划出窗口了，弹出队头以元素）
            if(!q.isEmpty() && i - k + 1 > q.peekFirst()) q.pollFirst();
            // 维护单调队列（当前元素 >= 队尾元素，则不断弹出，然后在加入，维护一个单调递增的序列）
            while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) q.pollLast();
            // 当前元素入队(加入队尾)
            q.addLast(i);
            // 当窗口大小达到k时，记录最大值
            if(i >= k - 1) res[idx ++] = nums[q.peekFirst()];
        }
        return res;
    }
}
